New plane-sweep algorithms for distance-based join queries in spatial databases

Efficient and effective processing of the distance-based join query (DJQ) is of great importance in spatial databases due to the wide area of applications that may address such queries (mapping, urban planning, transportation planning, resource management, etc.). The most representative and studied DJQs are the K Closest Pairs Query (KCPQ) and εDistance Join Query (εDJQ). These spatial queries involve two spatial data sets and a distance function to measure the degree of closeness, along with a given number of pairs in the final result (K) or a distance threshold (ε). In this paper, we propose four new plane-sweep-based algorithms for KCPQs and their extensions for εDJQs in the context of spatial databases, without the use of an index for any of the two disk-resident data sets (since, building and using indexes is not always in favor of processing performance). They employ a combination of plane-sweep algorithms and space partitioning techniques to join the data sets. Finally, we present results of an extensive experimental study, that compares the efficiency and effectiveness of the proposed algorithms for KCPQs and εDJQs. This performance study, conducted on medium and big spatial data sets (real and synthetic) validates that the proposed plane-sweep-based algorithms are very promising in terms of both efficient and effective measures, when neither inputs are indexed. Moreover, the best of the new algorithms is experimentally compared to the best algorithm that is based on the R-tree (a widely accepted access method), for KCPQs and εDJQs, using the same data sets. This comparison shows that the new algorithms outperform R-tree based algorithms, in most cases.     

Endogenous games with goals: side-payments among goal-directed agents

Boolean games have been developed as a paradigm for modelling societies of goal-directed agents. In boolean games agents exercise control over propositional variables and strive to achieve a goal formula whose realization might require the opponents’ cooperation. The presence of agents that are goal-directed makes it difficult for an external authority to be able to remove undesirable properties that are inconsistent with agents’ goals, as shown by recent contributions in the multi-agent literature. What this paper does is to analyse the problem of regulation of goal-direct agents from within the system, i.e., what happens when agents themselves are given the chance to negotiate the strategies to be played with one another. Concretely, we introduce endogenous games with goals, obtained coupling a general model of goal-directed agents (strategic games with goals) with a general model of pre-play negotiations (endogenous games) coming from game theory. Strategic games with goals are shown to have a direct correspondence with strategic games (Proposition 1) but, when side-payments are allowed in the pre-play phase, display a striking imbalance (Proposition 4). The effect of side-payments can be fully simulated by taxation mechanisms studied in the literature (Proposition 7), yet we show sufficient conditions under which outcomes can be rationally sustained without external intervention (Proposition 5). Also, integrating taxation mechanisms and side-payments, we are able to transform our starting models in such a way that outcomes that are theoretically sustainable thanks to a pre-play phase can be actually sustained even with limited resources (Proposition 8). Finally, we show how an external authority incentivising a group of agents can be studied as a special agent of an appropriately extended endogenous game with goals (Proposition 11).     

Learning about the opponent in automated bilateral negotiation: a comprehensive survey of opponent modeling techniques

A negotiation between agents is typically an incomplete information game, where the agents initially do not know their opponent’s preferences or strategy. This poses a challenge, as efficient and effective negotiation requires the bidding agent to take the other’s wishes and future behavior into account when deciding on a proposal. Therefore, in order to reach better and earlier agreements, an agent can apply learning techniques to construct a model of the opponent. There is a mature body of research in negotiation that focuses on modeling the opponent, but there exists no recent survey of commonly used opponent modeling techniques. This work aims to advance and integrate knowledge of the field by providing a comprehensive survey of currently existing opponent models in a bilateral negotiation setting. We discuss all possible ways opponent modeling has been used to benefit agents so far, and we introduce a taxonomy of currently existing opponent models based on their underlying learning techniques. We also present techniques to measure the success of opponent models and provide guidelines for deciding on the appropriate performance measures for every opponent model type in our taxonomy.     

Modeling culture in intelligent virtual agents

This work addresses the challenge of creating virtual agents that are able to portray culturally appropriate behavior when interacting with other agents or humans. Because culture influences how people perceive their social reality it is important to have agent models that explicitly consider social elements, such as existing relational factors. We addressed this necessity by integrating culture into a novel model for simulating human social behavior. With this model, we operationalized a particular dimension of culture—individualism versus collectivism—within the context of an interactive narrative scenario that is part of an agent-based tool for intercultural training. Using this scenario we conducted a cross-cultural study in which participants from a collectivistic country (Portugal) were compared with participants from an individualistic country (the Netherlands) in the way they perceived and interacted with agents whose behavior was either individualistic or collectivistic, according to the configuration of the proposed model. In the obtained results, Portuguese subjects rated the collectivistic agents more positively than the Dutch but both countries had a similarly positive opinion about the individualistic agents. This experiment sheds new light on how people from different countries differ when assessing the social appropriateness of virtual agents, while also raising new research questions on this matter.     

Business process compliance checking – applying and evaluating a generic pattern matching approach for conceptual models in the financial sector

Given the strong increase in regulatory requirements for business processes the management of business process compliance becomes a more and more regarded field in IS research. Several methods have been developed to support compliance checking of conceptual models. However, their focus on distinct modeling languages and mostly linear (i.e., predecessor-successor related) compliance rules may hinder widespread adoption and application in practice. Furthermore, hardly any of them has been evaluated in a real-world setting. We address this issue by applying a generic pattern matching approach for conceptual models to business process compliance checking in the financial sector. It consists of a model query language, a search algorithm and a corresponding modelling tool prototype. It is (1) applicable for all graph-based conceptual modeling languages and (2) for different kinds of compliance rules. Furthermore, based on an applicability check, we (3) evaluate the approach in a financial industry project setting against its relevance for decision support of audit and compliance management tasks.     

Simulating protection rackets: a case study of the Sicilian Mafia

Protection racketeering groups are powerful, deeply entrenched in multiple societies across the globe, and they harm the societies and economies in which they operate in multiple ways. These reasons make their dynamics important to understand and an objective of both scientific and application-oriented interest. Legal and social norm-based approaches arguably play significant roles in influencing protection racket dynamics. We propose an agent-based simulation model, the Palermo Scenario, to enrich our understanding of these influences and to test the effect of different policies on protection racket dynamics. Our model integrates the legal and the social norm-based approaches and uses a complex normative agent architecture that enables the analysis of both agents’ behaviours and mental normative representations driving behaviour. We demonstrate the usefulness of the model and the benefits of using this complex normative architecture through a case study of the Sicilian Mafia.     

A simulation framework for measuring robustness of incentive mechanisms and its implementation in reputation systems

In game theoretical analysis of incentive mechanisms, all players are assumed to be rational. Since it is likely that mechanism participants in the real world may not be fully rational, such mechanisms may not work as effectively as in the idealized settings for which they were designed. Therefore, it is important to evaluate the robustness of incentive mechanisms against various types of agents with bounded rational behaviors. Such evaluations would provide us with the information needed to choose mechanisms with desired properties in real environments. In this article, we first propose a general robustness measure, inspired by research in evolutionary game theory, as the maximal percentage of invaders taking non-equilibrium strategies such that the agents sustain the desired equilibrium strategy. We then propose a simulation framework based on evolutionary dynamics to empirically evaluate the equilibrium robustness. The proposed simulation framework is validated by comparing the simulated results with the analytical predictions based on a modified simplex analysis approach. Finally, we implement the proposed simulation framework for evaluating the robustness of incentive mechanisms in reputation systems for electronic marketplaces. The results from the implementation show that the evaluated mechanisms have high robustness against a certain non-equilibrium strategy, but is vulnerable to another strategy, indicating the need for designing more robust incentive mechanisms for reputation management in e-marketplaces.     

A coherence maximisation process for solving normative inconsistencies

Norms can be used in multi-agent systems for defining patterns of behaviour in terms of permissions, prohibitions and obligations that are addressed to agents playing a specific role. Agents may play different roles during their execution and they may even play different roles simultaneously. As a consequence, agents may be affected by inconsistent norms; e.g., an agent may be simultaneously obliged and forbidden to reach a given state of affairs. Dealing with this type of inconsistency is one of the main challenges of normative reasoning. Existing approaches tackle this problem by using a static and predefined order that determines which norm should prevail in the case where two norms are inconsistent. One main drawback of these proposals is that they allow only pairwise comparison of norms; it is not clear how agents may use the predefined order to select a subset of norms to abide by from a set of norms containing multiple inconsistencies. Furthermore, in dynamic and non-deterministic environments it can be difficult or even impossible to specify an order that resolves inconsistencies satisfactorily in all potential situations. In response to these two problems, we propose a mechanism with which an agent can dynamically compute a preference order over subsets of its competing norms by considering the coherence of its cognitive and normative elements. Our approach allows flexible resolution of normative inconsistencies, tailored to the current circumstances of the agent. Moreover, our solution can be used to determine norm prevalence among a set of norms containing multiple inconsistencies.     

Majority bargaining for resource division

We address the problem of how a set of agents can decide to share a resource, represented as a unit-sized pie. The pie can be generated by the entire set but also by some of its subsets. We investigate a finite horizon non-cooperative bargaining game, in which the players take it in turns to make proposals on how the resource should for this purpose be allocated, and the other players vote on whether or not to accept the allocation. Voting is modelled as a Bayesian weighted voting game with uncertainty about the players’ weights. The agenda, (i.e., the order in which the players are called to make offers), is defined exogenously. We focus on impatient players with heterogeneous discount factors. In the case of a conflict, (i.e., no agreement by the deadline), no player receives anything. We provide a Bayesian subgame perfect equilibrium for the bargaining game and conduct an ex-ante analysis of the resulting outcome. We show that the equilibrium is unique, computable in polynomial time, results in an instant Pareto optimal outcome, and, under certain conditions provides a foundation for the core and also the nucleolus of the Bayesian voting game. In addition, our analysis leads to insights on how an individual’s bargained share is influenced by his position on the agenda. Finally, we show that, if the conflict point of the bargaining game changes, then the problem of determining the non-cooperative equilibrium becomes NP-hard even under the perfect information assumption. Our research also reveals how this change in conflict point impacts on the above mentioned results.